#include <algorithm>
#include <iterator>
#include <iostream>
#include <math.h>
#include <limits>

const int THRESHOLD = 75;
const int CLASS_SIZE = 75;     /* minimum value for m */

void flashsort(float a[],int n,int m,int *ctr)
{
  /* declare variables */
  int *l,nmin,nmax,i,j,k,nmove,nx,mx;
  float c1,c2,flash,hold;    

  /* allocate space for the l vector */
  l=(int*)calloc(m,sizeof(int));
  
  /*Time measure*/
  struct timespec start, finish;
  static double ClassFormation, LeaderChoice, Permutation, InsertionSort;
  
  if (*ctr == 0)
  {
    ClassFormation=0;
    LeaderChoice=0;
    Permutation=0;
    InsertionSort=0;
  }

  /***** CLASS FORMATION ****/
  clock_gettime(CLOCK_MONOTONIC, &start);
  nmin=nmax=0;
  
  for (i=1 ; i<n ; i++)
  {
     if (a[i] < a[nmin])
     {
       nmin = i;       
     }
     else if (a[i] > a[nmax]) 
     {
        nmax = i;
     }
  }

  if ( (a[nmax]==a[nmin]) && (*ctr==0) )
  {
     std::cout << "All the numbers are identical, the list is sorted" << std::endl;
     return;
  }

  c1=((float)m-1.0)/(a[nmax]-a[nmin]) ;
  c2=a[nmin];

  l[0]=-1; /* since the base of the "a" (data) array is 0 */
  //for (k=1; k<m ; k++) l[k]=0;
  
  for (i=0; i<n ; i++)
  {
    //k=floor(c1*(a[i]-c2) );
    k=(c1*(a[i]-c2) );
    l[k]+=1;
   }

   for (k=1; k<m ; k++) 
   {
     //std::cout << l[k] << " ";
     l[k]+=l[k-1];     
   }
   //std::cout << std::endl;
   hold=a[nmax];
   a[nmax]=a[0];
   a[0]=hold; 
   
   clock_gettime(CLOCK_MONOTONIC, &finish);
   ClassFormation += (finish.tv_sec - start.tv_sec);
   ClassFormation += (finish.tv_nsec - start.tv_nsec) / 1000000000.0; 
   
   if (*ctr==0)
   {     
      std::cout << "Min: " << a[nmin] << " Max: " << a[0] << std::endl;
      std::cout << "Number of Classes: " << m << std::endl;
   
      int aMinCl=std::numeric_limits<int>::max();;
      int aMaxCl=std::numeric_limits<int>::min();;
      for (k=m-2; k>=1 ; k--) 
      {
	//std::cout << l[k] << " ";     
	aMinCl=std::min(aMinCl, l[k]-l[k-1]);
	aMaxCl=std::max(aMaxCl, l[k]-l[k-1]);
      }
      std::cout << "Class Size Min: " << aMinCl << " max size: " << aMaxCl << std::endl;
   }
   
   /**** PERMUTATION *****/        
   nmove=0;
   j=0;
   k=m-1;

   while(nmove<n-1)
   {
         
     clock_gettime(CLOCK_MONOTONIC, &start);	
      while  (j  >  l[k] )
      {
	j++;
	k=(c1*(a[j]-c2) ) ;
      }
      clock_gettime(CLOCK_MONOTONIC, &finish);
      LeaderChoice += (finish.tv_sec - start.tv_sec);
      LeaderChoice += (finish.tv_nsec - start.tv_nsec) / 1000000000.0;
      
      
      clock_gettime(CLOCK_MONOTONIC, &start);      
      flash=a[ j ] ;
      while ( j <= l[k] )
      {
	k=(c1*(flash-c2));
	hold=a[ l[k] ];
	a[ l[k] ] = flash;
	l[k]--;
	flash=hold;
	nmove++;
      }
      clock_gettime(CLOCK_MONOTONIC, &finish);
      Permutation += (finish.tv_sec - start.tv_sec);
      Permutation += (finish.tv_nsec - start.tv_nsec) / 1000000000.0;
   }

 /**** Choice of RECURSION or STRAIGHT INSERTION *****/
  
  for (k=0;k<(m-1);k++)
   if ( (nx = l[k+1]-l[k]) > THRESHOLD )  /* then use recursion */
   {
     (*ctr)++;
      flashsort(&a[l[k]+1],nx,(nx*0.05)+2,ctr);      
   }
   else  /* use insertion sort */
   {
     clock_gettime(CLOCK_MONOTONIC, &start);
      for (i=l[k+1]-1; i > l[k] ; i--)
	  if (a[i] > a[i+1])
	  {
	     hold=a[i];
	     j=i;
	     while  (hold  >  a[j+1] )  
	     {	       
	       a[j++]=a[j+1] ;	       
	     }
	     a[j]=hold;
	  }
       clock_gettime(CLOCK_MONOTONIC, &finish);
       InsertionSort+= (finish.tv_sec - start.tv_sec);
       InsertionSort+= (finish.tv_nsec - start.tv_nsec) / 1000000000.0;
   }
  free(l);   /* need to free the memory we grabbed for the l vector */
    
  if (*ctr==0)
  {
    std::cout << "ClassFormation: " << ClassFormation 
    << "\n LeaderChoice: " << LeaderChoice 
    << "\n Permutation: " << Permutation
    << "\n InsertionSort: "<< InsertionSort 
    << "\n Total Time: " << ClassFormation + LeaderChoice + Permutation +InsertionSort << std::endl;
  }
  
  (*ctr)--;
}